home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 November / EnigmA AMIGA RUN 02 (1995)(G.R. Edizioni)(IT)[!][issue 1995-11][Skylink CD].iso / earcd / program / gcc / ixemul-4.lha / ixemul-41.4 / network / utils.c < prev   
C/C++ Source or Header  |  1995-05-18  |  9KB  |  351 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)utils.c    5.3 (Berkeley) 3/3/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46.  
  47. /*
  48.  *  _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
  49.  *
  50.  *    This routine manages the statically allocated buffers in which we
  51.  *    return data to the user.
  52.  *
  53.  *    Parameters:
  54.  *        t -- btree from which to return datum
  55.  *        d -- DATUM to be returned to the user.
  56.  *        data -- data argument supplied by user for return
  57.  *        key -- key argument supplied by user for return
  58.  *
  59.  *    Returns:
  60.  *        RET_SUCCESS, RET_ERROR.
  61.  *
  62.  *    Side Effects:
  63.  *        May free and reallocate static buffers, if the data
  64.  *        we want to return is bigger than the space we have to
  65.  *        do so.
  66.  */
  67.  
  68. int
  69. _bt_buildret(t, d, data, key)
  70.     BTREE_P t;
  71.     DATUM *d;
  72.     DBT *data;
  73.     DBT *key;
  74. {
  75.     static int _data_s = 0;
  76.     static int _key_s = 0;
  77.     static char *_data = (char *) NULL;
  78.     static char *_key = (char *) NULL;
  79.     pgno_t chain;
  80.  
  81.     if (d->d_flags & D_BIGKEY) {
  82.         if (_key != (char *) NULL)
  83.             (void) free(_key);
  84.         (void) bcopy((char *) &(d->d_bytes[0]),
  85.                        (char *) &chain,
  86.                        sizeof(chain));
  87.         if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
  88.             return (RET_ERROR);
  89.         key->data = (u_char *)_key;
  90.         key->size = _key_s;
  91.     } else {
  92.         /* need more space for key? */
  93.         if (d->d_ksize > _key_s) {
  94.             if (_key != (char *) NULL)
  95.                 (void) free (_key);
  96.             if ((_key = (char *) malloc((unsigned) d->d_ksize))
  97.                 == (char *) NULL)
  98.                 return (RET_ERROR);
  99.             _key_s = d->d_ksize;
  100.         }
  101.  
  102.         key->data = (u_char *)_key;
  103.         if ((key->size = d->d_ksize) > 0)
  104.             (void) bcopy(&(d->d_bytes[0]),
  105.                      _key,
  106.                      (int) d->d_ksize);
  107.     }
  108.  
  109.     if (d->d_flags & D_BIGDATA) {
  110.         if (_data != (char *) NULL)
  111.             (void) free(_data);
  112.         (void) bcopy(&(d->d_bytes[d->d_ksize]),
  113.                        (char *) &chain,
  114.                        sizeof(chain));
  115.         if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
  116.             return (RET_ERROR);
  117.         data->data = (u_char *)_data;
  118.         data->size = _data_s;
  119.     } else {
  120.         /* need more space for data? */
  121.         if (d->d_dsize > _data_s) {
  122.             if (_data != (char *) NULL)
  123.                 (void) free (_data);
  124.             if ((_data = (char *) malloc((unsigned) d->d_dsize))
  125.                 == (char *) NULL)
  126.                 return (RET_ERROR);
  127.             _data_s = d->d_dsize;
  128.         }
  129.  
  130.         data->data = (u_char *)_data;
  131.  
  132.         if ((data->size = d->d_dsize) > 0)
  133.             (void) bcopy(&(d->d_bytes[d->d_ksize]),
  134.                       _data,
  135.                       (size_t) (d->d_dsize));
  136.     }
  137.  
  138.     return (RET_SUCCESS);
  139. }
  140.  
  141. /*
  142.  *  _BT_CMP -- Compare a key to a given item on the current page.
  143.  *
  144.  *    This routine is a wrapper for the user's comparison function.
  145.  *
  146.  *    Parameters:
  147.  *        t -- tree in which to do comparison
  148.  *        p -- pointer to one argument for the comparison function
  149.  *        n -- index of item to supply second arg to comparison function
  150.  *
  151.  *    Returns:
  152.  *        < 0 if p is < item at n
  153.  *        = 0 if p is = item at n
  154.  *        > 0 if p is > item at n
  155.  */
  156.  
  157. int
  158. _bt_cmp(t, p, n)
  159.     BTREE_P t;
  160.     char *p;
  161.     index_t n;
  162. {
  163.     BTHEADER *h;
  164.     IDATUM *id;
  165.     DATUM *d;
  166.     char *arg;
  167.     int ignore;
  168.     int free_arg;
  169.     pgno_t chain;
  170.     int r;
  171.  
  172.     h = t->bt_curpage;
  173.  
  174.     /*
  175.      *  The left-most key at any level of the tree on internal pages
  176.      *  is guaranteed (artificially, by the code here) to be less than
  177.      *  any user key.  This saves us from having to update the leftmost
  178.      *  key when the user inserts a new key in the tree smaller than
  179.      *  anything we've seen yet.
  180.      */
  181.  
  182.     if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
  183.         return (1);
  184.  
  185.     if (h->h_flags & F_LEAF) {
  186.         d = (DATUM *) GETDATUM(h,n);
  187.         if (d->d_flags & D_BIGKEY) {
  188.             free_arg = TRUE;
  189.             bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
  190.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  191.                 return (RET_ERROR);
  192.         } else {
  193.             free_arg = FALSE;
  194.             arg = &(d->d_bytes[0]);
  195.         }
  196.     } else {
  197.         id = (IDATUM *) GETDATUM(h,n);
  198.         if (id->i_flags & D_BIGKEY) {
  199.             free_arg = TRUE;
  200.             bcopy(&(id->i_bytes[0]),
  201.                   (char *) &chain,
  202.                   sizeof(chain));
  203.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  204.                 return (RET_ERROR);
  205.         } else {
  206.             free_arg = FALSE;
  207.             arg = &(id->i_bytes[0]);
  208.         }
  209.     }
  210.     r = (*(t->bt_compare))(p, arg);
  211.  
  212.     if (free_arg)
  213.         (void) free(arg);
  214.  
  215.     return (r);
  216. }
  217.  
  218. /*
  219.  *  _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
  220.  *
  221.  *    When we descend the tree, we keep track of parent pages in order
  222.  *    to handle splits on insertions.
  223.  *
  224.  *    Parameters:
  225.  *        t -- tree for which to push parent
  226.  *        pgno -- page number to push (_bt_push only)
  227.  *
  228.  *    Returns:
  229.  *        RET_SUCCESS, RET_ERROR.
  230.  */
  231.  
  232. int
  233. _bt_push(t, pgno)
  234.     BTREE_P t;
  235.     pgno_t pgno;
  236. {
  237.     BTSTACK *new;
  238.  
  239.     if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK)))
  240.         ==  (BTSTACK *) NULL)
  241.         return (RET_ERROR);
  242.     new->bts_pgno = pgno;
  243.     new->bts_next = t->bt_stack;
  244.     t->bt_stack = new;
  245.  
  246.     return (RET_SUCCESS);
  247. }
  248.  
  249. pgno_t
  250. _bt_pop(t)
  251.     BTREE_P t;
  252. {
  253.     BTSTACK *s;
  254.     pgno_t p = P_NONE;
  255.  
  256.     if ((s = t->bt_stack) != (BTSTACK *) NULL) {
  257.         p = s->bts_pgno;
  258.         t->bt_stack = s->bts_next;
  259.         (void) free ((char *) s);
  260.     }
  261.     return (p);
  262. }
  263.  
  264. #ifdef DEBUG
  265. void
  266. _btdump(tree)
  267.     BTREE tree;
  268. {
  269.     BTREE_P t = (BTREE_P) tree;
  270.     DATUM *d;
  271.     IDATUM *id;
  272.     BTHEADER *h;
  273.     pgno_t npages;
  274.     pgno_t i;
  275.     index_t cur, top;
  276.  
  277.     npages = t->bt_npages;
  278.     (void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
  279.         t->bt_fname, t->bt_s.bt_d.d_fd,
  280.         t->bt_psize, t->bt_curpage);
  281.     (void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
  282.     if (t->bt_flags & BTF_SEQINIT)
  283.         (void) printf("BTF_SEQINIT");
  284.     (void) printf(")\n");
  285.  
  286.     for (i = P_ROOT; i <= npages; i++) {
  287.         if (_bt_getpage(t, i) == RET_ERROR)
  288.             _punt();
  289.         h = t->bt_curpage;
  290.         top = NEXTINDEX(h);
  291.         (void) printf("    page %d:\n", i);
  292.         (void) printf("\tpgno %d prev %d next %d\n",
  293.             h->h_pgno, h->h_prevpg, h->h_nextpg);
  294.         (void) printf("\tlower %d upper %d nextind %d flags (",
  295.             h->h_lower, h->h_upper, top);
  296.         if (h->h_flags & F_LEAF)
  297.             (void) printf("F_LEAF");
  298.         else
  299.             (void) printf("<internal>");
  300.         if (h->h_flags & F_DIRTY)
  301.             (void) printf("|F_DIRTY");
  302.         if (h->h_flags & F_PRESERVE)
  303.             (void) printf("|F_PRESERVE");
  304.         if (h->h_flags & F_CONT) {
  305.             (void) printf("|F_CONT)");
  306.             if (h->h_prevpg == P_NONE) {
  307.                 size_t longsz;
  308.                 (void) bcopy((char *) &(h->h_linp[0]),
  309.                           (char *) &longsz,
  310.                           sizeof(longsz));
  311.                 printf("\n\t\t(chain start, data length %ld)",
  312.                     longsz);
  313.             }
  314.             printf("\n");
  315.             continue;
  316.         }
  317.         (void) printf(")\n");
  318.         for (cur = 0; cur < top; cur++) {
  319.             (void) printf("\t  [%d] off %d ", cur, h->h_linp[cur]);
  320.             if (h->h_flags & F_LEAF) {
  321.                 d = (DATUM *) GETDATUM(h,cur);
  322.                 (void) printf("ksize %d", d->d_ksize);
  323.                 if (d->d_flags & D_BIGKEY)
  324.                     (void) printf(" (indirect)");
  325.                 (void) printf("; dsize %d", d->d_dsize);
  326.                 if (d->d_flags & D_BIGDATA)
  327.                     (void) printf(" (indirect)");
  328.             } else {
  329.                 id = (IDATUM *) GETDATUM(h,cur);
  330.                 (void) printf("size %d pgno %d",
  331.                     id->i_size, id->i_pgno);
  332.                 if (id->i_flags & D_BIGKEY)
  333.                     (void) printf(" (indirect)");
  334.             }
  335.             (void) printf("\n");
  336.         }
  337.         (void) printf("\n");
  338.     }
  339. }
  340. #endif /* DEBUG */
  341.  
  342. #ifdef DEBUG
  343. _punt()
  344. {
  345.     int pid;
  346.  
  347.     pid = getpid();
  348.     (void) kill(pid, SIGILL);
  349. }
  350. #endif /* DEBUG */
  351.